package com.liunian.duplication1;

public class NumTrees96 {

	/**
	 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

	 示例 1：
	 输入：n = 3
	 输出：5

	 示例 2：
	 输入：n = 1
	 输出：1
	 */
	/**
	 dp[3]
	 dp[0] * dp[3]
	 dp[3] * dp[0]
	 dp[1] * dp[2]
	 dp[2] * dp[1]
	 */

	public int numTrees(int n) {
		int[] dp = new int[n + 1];
		dp[0] = 1;
		dp[1] = 1;
		for (int i = 2; i < n + 1; i++) {
			for (int j = 1; j <= i; j++) {
				dp[i] += dp[i - j] * dp[j - 1];
			}
		}
		return dp[n];
	}

	public static void main(String[] args) {
		NumTrees96 trees96 = new NumTrees96();
		System.out.println(trees96.numTrees(1));
	}

}
